import java.util.LinkedList;
import java.util.List;
import java.lang.Math;
//import java.util.Hashtable;

public class IDA_Star {
        public static final int inf = 10000;
    
        public IDA_Star(){}
        
        public static class DFS_Object{
                DFS_Object(){
                }
                DFS_Object(List<Action> s, int cost){
                        solution = s;
                        cost_limit = cost;
                }
                List<Action> solution;
                int cost_limit;
        }
        
        public static int heuristics(Battle game_state) {
            throw new UnsupportedOperationException();
        }

        public static DFS_Object IDA_Star_Run(Battle rootNode){
                int cost_limit = heuristics(rootNode);
                DFS_Object result;
                while (true){
                        result = DFS(0, rootNode, cost_limit, new LinkedList<Action>());
                        if(result.cost_limit == inf) return null;
                        if (result.solution != null) return result;
                        
                }
        }
        
        public static boolean is_goal_node(Battle node) {
            throw new UnsupportedOperationException();
        }
        
        public static int edgeCosts(Action succAction){
        	throw new UnsupportedOperationException();
        }
        
        public static DFS_Object DFS(int start_cost, Battle node, int cost_limit, LinkedList<Action> path_so_far){
                int minimum_cost = start_cost + heuristics(node);
                if(minimum_cost > cost_limit) return new DFS_Object(null, minimum_cost);
                if(is_goal_node(node)) return new DFS_Object(path_so_far, cost_limit);
                int next_cost_limit = inf;
                for (Action succAction: node.successors()){
                        Battle succNode = node.clone();
                        succAction.perform(succNode);
                        int newStartCost = start_cost + edgeCosts(succAction);
                        path_so_far.addLast(succAction);
                        DFS_Object path = DFS(newStartCost, succNode, cost_limit, path_so_far);
                        if (path.solution != null) return path;
                        next_cost_limit = Math.min(next_cost_limit, path.cost_limit);
                }
                return new DFS_Object(null, next_cost_limit);
        }
}